package com.lfg.leetcode.leetcode0;


public class No42Trap {

    public static void main(String[] args) {
        int ret = trap(new int[]{4, 2, 0, 3, 2, 5});
        System.out.println(ret);
    }

    public static int trap(int[] height) {
        int[] leftHeight = new int[height.length];
        int[] rightHeight = new int[height.length];
        leftHeight[0] = height[0];
        rightHeight[height.length - 1] = height[height.length - 1];
        for (int i = 1; i < height.length; i++) {
            leftHeight[i] = Math.max(leftHeight[i - 1], height[i]);
        }

        for (int i = height.length - 2; i >= 0; i--) {
            rightHeight[i] = Math.max(rightHeight[i + 1], height[i]);
        }
        int ret = 0;
        for (int i = 0; i < height.length; i++) {
            ret += Math.min(leftHeight[i], rightHeight[i]) - height[i];
        }

        return ret;
    }

    public static int trap2(int[] height) {
        int ret = 0;
        if (height.length == 0) {
            return ret;
        }
        int right = height.length - 1;
        int left = 0;
        for (int i = 0; i < right; i++) {
            if (height[i] != 0) {
                left = i;
                break;
            }
        }

        for (; right > left; right--) {
            if (height[right] != 0) {
                break;
            }
        }
        int index = 0;
        while (left < right) {
            if (height[left] < height[right]) {
                for (index = left + 1; index < right; index++) {
                    if (height[index] >= height[left]) {
                        break;
                    }
                }
                ret += left(height, index, left);
                left = index;
            } else {
                for (index = right - 1; index > left; index--) {
                    if (height[index] >= height[right]) {
                        break;
                    }
                }
                ret += right(height, index, right);
                right = index;
            }
        }

        return ret;
    }

    private static int right(int[] height, int l, int right) {
        int ret = 0;
        for (int n = right - 1; n > l; n--) {
            ret += height[right] - height[n];
        }
        return ret;
    }

    private static int left(int[] height, int i, int left) {
        int ret = 0;
        for (int n = left + 1; n < i; n++) {
            ret += height[left] - height[n];
        }
        return ret;
    }
}

